#include "UtilityPCH.h"
#include "UT_GeometrySubDivisionSurface.h"
#include "UT_MathHelper.h"
#include "UT_TAlgorithm.h"
#include "UT_Log.h"

using namespace Utility;
using namespace Memory;
// LoopSubdiv Macros
#define NEXT(i) (((i)+1)%3)
#define PREV(i) (((i)+2)%3)

struct UT_GeometrySubDivisionSurface::SDFace;
//--------------------------------------------------------------------
// UT_GeometrySubDivisionSurface::SDVertex
//--------------------------------------------------------------------
struct UT_GeometrySubDivisionSurface::SDVertex : public Memory::MM_DefaultObject
{
	// SDVertex Constructor
	SDVertex(UT_Point3Float pt = UT_Point3Float(0,0,0))
		: P(pt), startFace(NULL), child(NULL),
		regular(false), boundary(false) { }

	// SDVertex Methods
	int32_t		valence();
	void		oneRing(UT_Point3Float *P);

	// SDVertex Data
	UT_Point3Float									P;
	UT_GeometrySubDivisionSurface::SDFace*			startFace;
	UT_GeometrySubDivisionSurface::SDVertex*		child;
	bool											regular, boundary;
};
//--------------------------------------------------------------------
// UT_GeometrySubDivisionSurface::SDFace
//--------------------------------------------------------------------
struct UT_GeometrySubDivisionSurface::SDFace : public Memory::MM_DefaultObject
{
	// SDFace Constructor
	SDFace() 
	{
		int32_t i;
		for (i = 0; i < 3; ++i) 
		{
			v[i] = NULL;
			f[i] = NULL;
		}
		for (i = 0; i < 4; ++i)
			children[i] = NULL;
	}

	// SDFace Methods
	int32_t vnum(UT_GeometrySubDivisionSurface::SDVertex *vert) const 
	{
		for (int32_t i = 0; i < 3; ++i)
			if (v[i] == vert) return i;

		GfxWriteLog(LOG_S_DEFAULT_ERROR,"Basic logic error in SDFace::vnum()");

		return -1;
	}
	UT_GeometrySubDivisionSurface::SDFace *nextFace(UT_GeometrySubDivisionSurface::SDVertex *vert) { return f[vnum(vert)]; }
	UT_GeometrySubDivisionSurface::SDFace *prevFace(UT_GeometrySubDivisionSurface::SDVertex *vert) { return f[PREV(vnum(vert))];}
	UT_GeometrySubDivisionSurface::SDVertex *nextVert(UT_GeometrySubDivisionSurface::SDVertex *vert) { return v[NEXT(vnum(vert))];}
	UT_GeometrySubDivisionSurface::SDVertex *prevVert(UT_GeometrySubDivisionSurface::SDVertex *vert) { return v[PREV(vnum(vert))];}
	UT_GeometrySubDivisionSurface::SDVertex *otherVert(UT_GeometrySubDivisionSurface::SDVertex *v0, UT_GeometrySubDivisionSurface::SDVertex *v1)
	{
		for (int32_t i = 0; i < 3; ++i)
			if (v[i] != v0 && v[i] != v1)
				return v[i];
		GfxWriteLog(LOG_S_DEFAULT_ERROR,"Basic logic error in SDVertex::otherVert()");
		return NULL;
	}

	UT_GeometrySubDivisionSurface::SDVertex *v[3];
	UT_GeometrySubDivisionSurface::SDFace *f[3];
	UT_GeometrySubDivisionSurface::SDFace *children[4];
};
//--------------------------------------------------------------------
// UT_GeometrySubDivisionSurface::SDEdge
//--------------------------------------------------------------------
struct UT_GeometrySubDivisionSurface::SDEdge : public Memory::MM_DefaultObject
{
	// SDEdge Constructor
	SDEdge(UT_GeometrySubDivisionSurface::SDVertex* v0 = NULL,UT_GeometrySubDivisionSurface::SDVertex* v1 = NULL) 
	{
		v[0] = ut_min(v0, v1);
		v[1] = ut_max(v0, v1);
		f[0] = f[1] = NULL;
		f0edgeNum = -1;
	}

	// SDEdge Comparison Function
	bool operator<(const SDEdge &e2) const 
	{
		if (v[0] == e2.v[0]) 
			return v[1] < e2.v[1];
		return v[0] < e2.v[0];
	}

	UT_GeometrySubDivisionSurface::SDVertex*	v[2];
	UT_GeometrySubDivisionSurface::SDFace*		f[2];
	int32_t											f0edgeNum;
};
//--------------------------------------------------------------------
// Inline Functions
//--------------------------------------------------------------------
inline int32_t UT_GeometrySubDivisionSurface::SDVertex::valence() 
{
	SDFace *f = startFace;
	if (!boundary) 
	{
		// Compute valence of interior vertex
		int32_t nf = 1;
		while ((f = f->nextFace(this)) != startFace)
			++nf;
		return nf;
	}
	else 
	{
		// Compute valence of boundary vertex
		int32_t nf = 1;
		while ((f = f->nextFace(this)) != NULL)
			++nf;
		f = startFace;
		while ((f = f->prevFace(this)) != NULL)
			++nf;
		return nf+1;
	}
}
//--------------------------------------------------------------------
void UT_GeometrySubDivisionSurface::SDVertex::oneRing(UT_Point3Float *P)
{
	if (!boundary) 
	{
		// Get one-ring vertices for interior vertex
		SDFace *face = startFace;
		do 
		{
			*P++ = face->nextVert(this)->P;
			face = face->nextFace(this);
		} while (face != startFace);
	}
	else
	{
		// Get one-ring vertices for boundary vertex
		SDFace *face = startFace, *f2;
		while ((f2 = face->nextFace(this)) != NULL)
			face = f2;
		*P++ = face->nextVert(this)->P;
		do 
		{
			*P++ = face->prevVert(this)->P;
			face = face->prevFace(this);
		} while (face != NULL);
	}
}
//--------------------------------------------------------------------
//--------------------------------------------------------------------
UT_GeometrySubDivisionSurface::UT_GeometrySubDivisionSurface(const UT_Transform *o2w, const UT_Transform *w2o, bool bReverseOrientation, 
	int32_t iTriangleNum,int32_t iVertexNum, 
	const int32_t* piIndices, const UT_Point3Float* pkVertices, int32_t iLevel)
	: UT_GeometryBase(o2w, w2o, bReverseOrientation)
{
	m_iLevels = iLevel
		;
	// Allocate _Subdiv_ vertices and faces
	int32_t i;
	SDVertex *verts = MM_NEW SDVertex[iVertexNum];
	for (i = 0; i < iVertexNum; ++i) 
	{
		verts[i] = SDVertex(pkVertices[i]);
		m_kVertices.AddLast(&verts[i]);
	}

	SDFace *fs	= MM_NEW SDFace[iTriangleNum];
	for (i = 0; i < iTriangleNum; ++i)
		m_kFaces.AddLast(&fs[i]);

	// Set face to vertex pointers
	const int32_t *vp = piIndices;
	for (i = 0; i < iTriangleNum; ++i) 
	{
		SDFace *f = m_kFaces.GetAt(i);
		for (int32_t j = 0; j < 3; ++j) 
		{
			SDVertex *v		= m_kVertices.GetAt(vp[j]);
			f->v[j]			= v;
			v->startFace	= f;
		}
		vp += 3;
	}

	// Set neighbor pointers in _faces_
	UT_TSet<SDEdge> edges;
	for (i = 0; i < iTriangleNum; ++i) 
	{
		SDFace *f = m_kFaces.GetAt(i);
		for (int32_t edgeNum = 0; edgeNum < 3; ++edgeNum)
		{
			// Update neighbor pointer for _edgeNum_
			int32_t v0 = edgeNum, v1 = NEXT(edgeNum);
			SDEdge e(f->v[v0], f->v[v1]);
			if (edges.Find(e) == edges.GetEnd()) 
			{
				// Handle new edge
				e.f[0] = f;
				e.f0edgeNum = edgeNum;
				edges.Add(e);
			}
			else
			{
				// Handle previously seen edge
				e = *edges.Find(e);
				e.f[0]->f[e.f0edgeNum] = f;
				f->f[edgeNum] = e.f[0];
				edges.Remove(e);
			}
		}
	}

	// Finish vertex initialization
	for (i = 0; i < iVertexNum; ++i)
	{
		SDVertex *v = m_kVertices.GetAt(i);
		SDFace *f = v->startFace;
		do 
		{
			f = f->nextFace(v);
		}
		while (f && f != v->startFace);

		v->boundary = (f == NULL);
		if (!v->boundary && v->valence() == 6)
			v->regular = true;
		else if (v->boundary && v->valence() == 4)
			v->regular = true;
		else
			v->regular = false;
	}
}
//--------------------------------------------------------------------
UT_GeometrySubDivisionSurface::~UT_GeometrySubDivisionSurface()
{
	MM_DELETE[] m_kVertices.GetAt(0);
	MM_DELETE[] m_kFaces.GetAt(0);
}
//--------------------------------------------------------------------
UT_BBOX_AABB UT_GeometrySubDivisionSurface::GetObjectBound() const
{
	UT_BBOX_AABB b;
	for (uint32_t i = 0; i < m_kVertices.GetSize(); i++)
		b = UT_MathHelper::Union(b, m_kVertices.GetAt(i)->P);
	return b;
}
//--------------------------------------------------------------------
UT_BBOX_AABB UT_GeometrySubDivisionSurface::GetWorldBound() const 
{
	UT_BBOX_AABB b;
	for (uint32_t i = 0; i < m_kVertices.GetSize(); i++)
		b = UT_MathHelper::Union(b, (*m_pkObjectToWorld)(m_kVertices.GetAt(i)->P));
	return b;
}
//--------------------------------------------------------------------
void UT_GeometrySubDivisionSurface::Refine(UT_TVector<UT_SmartPointer<UT_GeometryBase>>& rkRefinedVector) const
{
	UT_TVector<SDFace *> f = m_kFaces;
	UT_TVector<SDVertex *> v = m_kVertices;
	MM_MemoryArena	kMemoryArena;

	for (int32_t i = 0; i < m_iLevels; ++i)
	{
		// Update _f_ and _v_ for next level of subdivision
		UT_TVector<SDFace *>	newFaces;
		UT_TVector<SDVertex *>	newVertices;

		// Allocate next level of children in mesh tree
		for (uint32_t j = 0; j < v.GetSize(); ++j)
		{
			v.GetAt(j)->child = kMemoryArena.Alloc<SDVertex>();
			v.GetAt(j)->child->regular = v.GetAt(j)->regular;
			v.GetAt(j)->child->boundary = v.GetAt(j)->boundary;
			newVertices.AddLast(v.GetAt(j)->child);
		}
		for (uint32_t j = 0; j < f.GetSize(); ++j)
		{
			for (int32_t k = 0; k < 4; ++k) 
			{
				f.GetAt(j)->children[k] = kMemoryArena.Alloc<SDFace>();
				newFaces.AddLast(f.GetAt(j)->children[k]);
			}
		}

		// Update vertex positions and create new edge vertices

		// Update vertex positions for even vertices
		for (uint32_t j = 0; j < v.GetSize(); ++j)
		{
			if (!v.GetAt(j)->boundary)
			{
				// Apply one-ring rule for even vertex
				if (v.GetAt(j)->regular)
					v.GetAt(j)->child->P = _weightOneRing(v.GetAt(j), 1.f/16.f);
				else
					v.GetAt(j)->child->P = _weightOneRing(v.GetAt(j), _beta(v.GetAt(j)->valence()));
			}
			else
			{
				// Apply boundary rule for even vertex
				v.GetAt(j)->child->P = _weightBoundary(v.GetAt(j), 1.f/8.f);
			}
		}

		// Compute new odd edge vertices
		UT_TMap<SDEdge, SDVertex *> edgeVerts;
		for (uint32_t j = 0; j < f.GetSize(); ++j)
		{
			SDFace *face = f.GetAt(j);
			for (int32_t k = 0; k < 3; ++k) 
			{
				// Compute odd vertex on _k_th edge
				SDEdge edge(face->v[k], face->v[NEXT(k)]);
				SDVertex *vert = edgeVerts.GetAt(edge);
				if (!vert)
				{
					// Create and initialize new odd vertex
					vert = MM_NEW SDVertex;
					newVertices.AddLast(vert);
					vert->regular = true;
					vert->boundary = (face->f[k] == NULL);
					vert->startFace = face->children[3];

					// Apply edge rules to compute new vertex position
					if (vert->boundary)
					{
						vert->P =  0.5f * edge.v[0]->P;
						vert->P += 0.5f * edge.v[1]->P;
					}
					else 
					{
						vert->P =  3.f/8.f * edge.v[0]->P;
						vert->P += 3.f/8.f * edge.v[1]->P;
						vert->P += 1.f/8.f * face->otherVert(edge.v[0], edge.v[1])->P;
						vert->P += 1.f/8.f *
							face->f[k]->otherVert(edge.v[0], edge.v[1])->P;
					}
					edgeVerts.Add(edge,vert);
				}
			}
		}

		// Update new mesh topology

		// Update even vertex face pointers
		for (uint32_t j = 0; j < v.GetSize(); ++j) 
		{
			SDVertex *vert = v.GetAt(j);
			int32_t vertNum = vert->startFace->vnum(vert);
			vert->child->startFace =
				vert->startFace->children[vertNum];
		}

		// Update face neighbor pointers
		for (uint32_t j = 0; j < f.GetSize(); ++j) 
		{
			SDFace *face = f.GetAt(j);
			for (int32_t k = 0; k < 3; ++k)
			{
				// Update children _f_ pointers for siblings
				face->children[3]->f[k] = face->children[NEXT(k)];
				face->children[k]->f[NEXT(k)] = face->children[3];

				// Update children _f_ pointers for neighbor children
				SDFace *f2 = face->f[k];
				face->children[k]->f[k] =
					f2 ? f2->children[f2->vnum(face->v[k])] : NULL;
				f2 = face->f[PREV(k)];
				face->children[k]->f[PREV(k)] =
					f2 ? f2->children[f2->vnum(face->v[k])] : NULL;
			}
		}

		// Update face vertex pointers
		for (uint32_t j = 0; j < f.GetSize(); ++j)
		{
			SDFace *face = f.GetAt(j);
			for (int32_t k = 0; k < 3; ++k) 
			{
				// Update child vertex pointer to new even vertex
				face->children[k]->v[k] = face->v[k]->child;

				// Update child vertex pointer to new odd vertex
				SDVertex *vert = edgeVerts.GetAt(SDEdge(face->v[k], face->v[NEXT(k)]));
				face->children[k]->v[NEXT(k)] = vert;
				face->children[NEXT(k)]->v[k] = vert;
				face->children[3]->v[k] = vert;
			}
		}

		// Prepare for next level of subdivision
		f = newFaces;
		v = newVertices;
	}
	// Push vertices to limit surface
	UT_Point3Float *Plimit = MM_NEW UT_Point3Float[v.GetSize()];
	for (uint32_t i = 0; i < v.GetSize(); ++i)
	{
		if (v.GetAt(i)->boundary)
			Plimit[i] =  _weightBoundary(v.GetAt(i), 1.f/5.f);
		else
			Plimit[i] =  _weightOneRing(v.GetAt(i), _gamma(v.GetAt(i)->valence()));
	}
	for (uint32_t i = 0; i < v.GetSize(); ++i)
		v.GetAt(i)->P = Plimit[i];

	// Compute vertex tangents on limit surface
	UT_TVector<UT_Normal3Float> Ns;
	Ns.ReserveCapacity(v.GetSize());
	UT_TVector<UT_Point3Float>  Pring(16, UT_Point3Float());
	
	for (uint32_t i = 0; i < v.GetSize(); ++i) 
	{
		SDVertex *vert = v.GetAt(i);
		UT_Vec3Float S(0,0,0), T(0,0,0);
		int32_t valence = vert->valence();
		if (valence > (int32_t)Pring.GetSize())
			Pring.Resize(valence);
		vert->oneRing(&Pring.GetAt(0));
		if (!vert->boundary) 
		{
			// Compute tangents of interior face
			for (int32_t k = 0; k < valence; ++k)
			{
				S += UT_MathHelper::Cos(2.f*UT_MathDefine::_PI*k/valence) * UT_Vec3Float(Pring.GetAt(k));
				T += UT_MathHelper::Sin(2.f*UT_MathDefine::_PI*k/valence) * UT_Vec3Float(Pring.GetAt(k));
			}
		} 
		else 
		{
			// Compute tangents of boundary face
			S = Pring.GetAt(valence-1) - Pring.GetAt(0);
			if (valence == 2)
				T = UT_Vec3Float(Pring.GetAt(0) + Pring.GetAt(1) - 2 * vert->P);
			else if (valence == 3)
				T = Pring.GetAt(1) - vert->P;
			else if (valence == 4) // regular
				T = UT_Vec3Float(-1*Pring.GetAt(0) + 2*Pring.GetAt(1) + 2*Pring.GetAt(2) +
				-1*Pring.GetAt(3) + -2*vert->P);
			else
			{
				float theta = UT_MathDefine::_PI / float(valence-1);
				T = UT_Vec3Float(UT_MathHelper::Sin(theta) * (Pring.GetAt(0) + Pring.GetAt(valence-1)));
				for (int32_t k = 1; k < valence-1; ++k)
				{
					float wt = (2*UT_MathHelper::Cos(theta) - 2) * UT_MathHelper::Sin((k) * theta);
					T += UT_Vec3Float(wt * Pring.GetAt(k));
				}
				T = -T;
			}
		}
		Ns.AddLast(UT_Normal3Float(UT_MathHelper::Cross(S, T)));
	}

	// Create _TriangleMesh_ from subdivision mesh
	uint32_t ntris = uint32_t(f.GetSize());
	int32_t *verts = (int32_t*)MM_STAND_ALLOC(3*ntris*sizeof(int32_t));
	int32_t *vp	   = verts;
	uint32_t totVerts = uint32_t(v.GetSize());
	UT_TMap<SDVertex *, int32_t> usedVerts;
	for (uint32_t i = 0; i < totVerts; ++i)
		usedVerts.GetAt(v.GetAt(i)) = i;
	for (uint32_t i = 0; i < ntris; ++i)
	{
		for (int32_t j = 0; j < 3; ++j)
		{
			*vp = usedVerts.GetAt(f.GetAt(i)->v[j]);
			++vp;
		}
	}
	/*ParamSet paramSet;
	paramSet.AddInt("indices", verts, 3*ntris);
	paramSet.AddPoint("P", Plimit, totVerts);
	paramSet.AddNormal("N", &Ns[0], int32_t(Ns.size()));
	rkRefinedVector.AddLast(CreateTriangleMeshShape(ObjectToWorld,
		WorldToObject, ReverseOrientation, paramSet));*/

	MM_DELETE[] Plimit;
	MM_STAND_DEALLOC(verts);
}
//--------------------------------------------------------------------
UT_Point3Float UT_GeometrySubDivisionSurface::_weightOneRing(SDVertex *vert, float beta) 
{
	// Put _vert_ one-ring in _Pring_
	int32_t valence			= vert->valence();
	UT_Point3Float *Pring	= MM_NEW UT_Point3Float[valence];
	vert->oneRing(Pring);
	UT_Point3Float P		= (1 - valence * beta) * vert->P;
	for (int32_t i = 0; i < valence; ++i)
		P += beta * Pring[i];
	return P;
}
//--------------------------------------------------------------------
UT_Point3Float UT_GeometrySubDivisionSurface::_weightBoundary(SDVertex *vert, float beta)
{
	// Put _vert_ one-ring in _Pring_
	int32_t valence = vert->valence();
	UT_Point3Float *Pring = MM_NEW UT_Point3Float[valence];
	vert->oneRing(Pring);
	UT_Point3Float P = (1-2*beta) * vert->P;
	P += beta * Pring[0];
	P += beta * Pring[valence-1];
	return P;
}
//--------------------------------------------------------------------
#undef NEXT 
#undef PREV 


























